#define _CRT_SECURE_NO_WARNINGS

#include "HashMap.h"


//哈希函数
uint32_t hash(const void* key, int len, uint32_t seed) 
{
    const uint32_t m = 0x5bd1e995;
    const int r = 24;
    uint32_t h = seed ^ len;
    const unsigned char* data = (const unsigned char*)key;

    while (len >= 4) {
        uint32_t k = *(uint32_t*)data;

        k *= m;
        k ^= k >> r;
        k *= m;

        h *= m;
        h ^= k;

        data += 4;
        len -= 4;
    }

    switch (len)
    {
    case 3: h ^= data[2] << 16;
    case 2: h ^= data[1] << 8;
    case 1: h ^= data[0];
        h *= m;
    };

    h ^= h >> 13;
    h *= m;
    h ^= h >> 15;

    return h;
}

//���캯��
HashMap* hashmap_create(void)
{
    HashMap* p = calloc(1, sizeof(HashMap));
    if (p == NULL)
    {
        printf("Error: calloc failed\n");
        exit(1);
    }

    Entry** q = calloc(DEFAULT_CAPACITY, sizeof(Entry*));
    if (p == NULL)
    {
        printf("Error: calloc failed\n");
        exit(1);
    }

    p->capacity = DEFAULT_CAPACITY;
    p->table = q;
    p->hashseed = (uint32_t)time(NULL);
    return p;
}

//��������
void hashmap_destroy(HashMap* map)
{
    //�ͷŵ�����
    for (int i = 0; i < map->capacity; ++i)
    {
        while (map->table[i] != NULL)
        {
            Entry* p = map->table[i]->next;
            free(map->table[i]);
            map->table[i] = p;
        }
    }
    //�ͷ�ջ
    free(map->table);
    free(map);
}

//����Ԫ��
V* hashmap_put(HashMap* map, K key, V* val)
{
    uint32_t temp_1 = hash(key, strlen(key), map->hashseed) % map->capacity;

    Entry* p = map->table[temp_1];
    while (p != NULL)
    {
        //�ҵ��ؼ���
        if (strcmp(p->key, key)==0)
        {
            V old_val = p->val;
            p->val = val;
            return old_val;
        }
        p = p->next;
    }
    //û���ҵ��ؼ���
    //�ƶ�ȫ��Ԫ��
    if ((double)map->capacity / map->size <= LOAD_FACTOR)
    {
        Entry** q = calloc(map->capacity << 1, sizeof(Entry*));
        if (q == NULL)
        {
            printf("Error: calloc failed\n");
            exit(1);
        }
        //��������seedֵ
        map->hashseed = (uint32_t)time(NULL);
        //�����µĹ�ϣ�����ƶ�Ԫ�ص��µ�������
        for (int i = 0; i < map->capacity; ++i)
        {
            while (map->table[i] != NULL)
            {
                Entry* r = map->table[i]->next;
                uint32_t temp_2 = hash(map->table[i]->key, strlen(map->table[i]->key), map->hashseed);
                map->table[i]->next = q[temp_2 % (map->capacity << 1)];
                q[temp_2 % (map->capacity << 1)] = map->table[i];
                map->table[i] = r;
            }
        }
        free(map->table);
        map->table = q;
        map->capacity <<= 1;
    }
    //������Ԫ��
    Entry* new_entry = malloc(sizeof(Entry));
    if (new_entry == NULL)
    {
        printf("Error: calloc failed\n");
        exit(1);
    }
    new_entry->key = key;
    new_entry->val = val;
    uint32_t temp_3 = hash(key, strlen(key), map->hashseed) % map->capacity;
    new_entry->next = map->table[temp_3];
    map->table[temp_3] = new_entry;
    map->size++;
    return NULL;
}

//����Ԫ��
V* hashmap_get(HashMap* map, K key)
{
    uint32_t temp = hash(key, strlen(key), map->hashseed);
    Entry* p = map->table[temp % map->capacity];

    while (p != NULL)
    {
        if (strcmp(p->key, key) == 0)
            return p->val;
        p = p->next;
    }

    printf("Not %s\n", key);
    return NULL;
}

//ɾ��Ԫ��
void hashmap_delete(HashMap* map, K key)
{
    uint32_t temp = hash(key, strlen(key), map->hashseed);
    if (map->table[temp % map->capacity] == NULL)
    {
        printf("Not %s\n", key);
        return;
    }

    Entry* p = map->table[temp % map->capacity];
    if (p->next == NULL)
    {
        if (strcmp(p->key, key) == 0)
        {
            free(p);
            map->size--;
            map->table[temp % map->capacity] = NULL;
            return;
        }
    }

    Entry* q = p->next;
    while (q != NULL)
    {
        if (strcmp(q->key, key) == 0)
        {
            p->next = q->next;
            map->size--;
            free(q);
            return;
        }
        p = q;
        q = q->next;
    }

    printf("Not %s\n", key);
}